#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include "kernel_list.h"

// 设计大结构体
struct node
{
    int data;
    struct list_head list; // 标准小结构体
};

struct node *init_list()
{
    struct node *head = calloc(1, sizeof(struct node));
    if(head != NULL)
    {
        INIT_LIST_HEAD(&head->list);
    }
    return head;
}

struct node *new_node(int data)
{
    struct node *new = calloc(1, sizeof(struct node));
    if(new != NULL)
    {
        new->data = data;
        INIT_LIST_HEAD(&new->list);
    }
    return new;
}

void show(struct node *head)
{
    struct list_head *pos;
    struct node *p;
    list_for_each(pos, &head->list)
    {
        p = list_entry(pos, struct node, list);
        printf("%d\t", p->data);
    }
    printf("\n");
}

void rearrange(struct node *head)
{
    // 从后往前遍历
    struct list_head *pos, *k=head->list.prev;
    struct node *p;
    list_for_each_prev(pos, &head->list)
    {
        p = list_entry(pos, struct node, list);

        // 1. 遇到偶数，则移动到链表末尾，然后定位到上一个奇数的位置
        if(p->data%2 == 0)
        {
            list_move_tail(pos, &head->list);
            pos = k; // 为了防止初次判定偶数时k为野指针，k必须初始化指向末尾
        }

        // 2. 遇到奇数，则记录下位置
        else
        {
            k = pos;
        }

    }
}

int main(int argc, char const *argv[])
{
    // 创建空链表
    struct node *head = init_list();

    int n;
    scanf("%d", &n);

    for(int i=1; i<=n; i++)
    {
        struct node *new = new_node(i);
        list_add_tail(&new->list, &head->list);
    }
    show(head);

    rearrange(head);
    show(head);

    return 0;
}
